From e91316d4cf72b2f89547237fecd9b6a8a1bc3512 Mon Sep 17 00:00:00 2001 From: =?utf8?q?=C3=98yvind=20Kol=C3=A5s?= Date: Tue, 12 Sep 2017 22:33:15 +0200 Subject: [PATCH] babl: replace trc lut inverter with binary search Much faster and much more accurate. --- babl/babl-trc.c | 29 ++++++++++++++++------------- 1 file changed, 16 insertions(+), 13 deletions(-) diff --git a/babl/babl-trc.c b/babl/babl-trc.c index 1a98889..ad40384 100644 --- a/babl/babl-trc.c +++ b/babl/babl-trc.c @@ -598,21 +598,24 @@ babl_trc_new (const char *name, for (j = 0; j < n_lut; j++) { - float k; - float best_guess = 1.0; - float best_diff = 1.0; - for (k = 0.0; k <= 1.0; k+=0.0001) /* XXX: a binary search would be faster */ + int k; + double min = 0.0; + double max = 1.0; + for (k = 0; k < 16; k++) { - float guess = babl_trc_lut_to_linear (BABL(&trc_db[i]), k); - float diff = fabs (guess - (j / (n_lut-1.0))); - if (diff < best_diff) - { - best_diff = diff; - best_guess = k; - } + double guess = (min + max) / 2; + float reversed_index = babl_trc_lut_to_linear (BABL(&trc_db[i]), guess) * (n_lut-1.0); + + if (reversed_index < j) + { + min = guess; + } + else if (reversed_index > j) + { + max = guess; + } } - - trc_db[i].inv_lut[j] = best_guess; + trc_db[i].inv_lut[j] = (min + max) / 2; } } -- 2.30.2